package demo8;

import java.util.Arrays;

class Sort {

    public void InsertSort(int[] arr) {
        for(int i = 1; i < arr.length; i++) {
            int insert = arr[i];
            int j = i-1;
            while(j>=0) {
                if(arr[j] > insert) {
                    arr[j + 1] = arr[j];
                    j--;
                } else {
                    break;
                }
            }
            arr[j+1] = insert;
        }
    }

//    //堆排
//    public void heapSort(int[] arr) {
//        for(int i = arr.length/2-1;i>=0;i--) {
//            adjustHeap(arr,i,arr.length);
//        }
//
//        for(int i = arr.length-1;i>0;i--) {
//            int tmp = arr[0];
//            arr[0] = arr[i];
//            arr[i] = tmp;
//            adjustHeap(arr,0,i);
//        }
//    }
//    public void adjustHeap(int[] arr,int i,int len) {
//        int tmp = arr[i];
//        for(int k = 2*i+1;k<len;k=2*k+1) {
//            if(k+1 < len && arr[k+1] > arr[k]) {
//                k++;
//            }
//            if(arr[k]>tmp) {
//                arr[i] = arr[k];
//                i = k;
//            } else {
//                break;
//            }
//        }
//        arr[i] = tmp;
//    }

//
//    //堆排
//    public void heapSort(int[] arr) {
//        createBigHeap(arr);
//        int end = arr.length - 1;
//        while(end > 0) {
//            swap(arr, 0, end);
//            adjustDown(arr, 0, end);
//            end--;
//        }
//    }
//
//    private void createBigHeap(int[] arr) {
//        int len = arr.length;
//        for(int parent = (len - 1 - 1) / 2; parent >= 0; parent--) {
//            //对每一颗子树向下调整
//            adjustDown(arr, parent, len);
//        }
//    }
//
//    private void adjustDown(int[] arr, int parent, int len) {
//        int child = parent * 2 + 1;
//        while(child < len) {
//            if(child + 1 < len && arr[child] < arr[child + 1]) {
//                child++;
//            }
//            if(arr[child] > arr[parent]) {
//                swap(arr, child, parent);
//                parent = child;
//                child = child * 2 + 1;
//            } else {
//                break;
//            }
//        }
//    }
//
//    private void swap(int[] arr, int child, int parent) {
//        int tmp = arr[child];
//        arr[child] = arr[parent];
//        arr[parent] = tmp;
//    }


    //堆排序
    public void heapSort(int[] arr) {
        //建立一个大根堆
        createBigHeap(arr);
        //每次和最后一个元素进行交换(作为已排好序的元素)，并继续向下调整成大根堆
        for(int i = arr.length - 1; i > 0; i--) {
            swap(arr, 0, i);
            adjustDown(arr, 0, i);
        }
    }

    private void createBigHeap(int[] arr) {
        int end = arr.length;
        //从最后一个子树开始对每一刻子树都进行向下调整
        for(int parent = (end - 1 - 1) / 2; parent >= 0; parent--) {
            adjustDown(arr, parent, end);
        }
    }

    private void adjustDown(int[] arr, int parent, int end) {
        int child = parent * 2 + 1;
        while(child < end) {
            if(child + 1 < end && arr[child] < arr[child + 1]) {
                child++;
            }
            if(arr[child] > arr[parent]) {
                swap(arr, child, parent);
                parent = child;
                child = child * 2 + 1;
            } else {
                break;
            }
        }
    }

    private void swap(int[] arr, int child, int parent) {
        int tmp = arr[child];
        arr[child] = arr[parent];
        arr[parent] = tmp;
    }

}

public class Solution {

    public static void main(String[] args) {
        int[] arr = {2,5,7,8,0,1,9,3,4,6};
        Sort sort = new Sort();
        sort.heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }

}
